package cn.cxq.learning.array;

import java.util.Arrays;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/a1eafeb5a7764a43bd3251ed572d90c4?toCommentId=9187726
 * 来源：牛客网
 * <p>
 * [编程题]牛牛的分配
 * 热度指数：177时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
 * 算法知识视频讲解
 * 长度为n的数组，每次可以选择若干元素使元素的值变为这些元素的和的平均值
 * 给出数组和数字x，求经过操作数组中最多有多少数字不小于x
 * <p>
 * <p>
 * 示例1
 * 输入
 * 3,7,[9,4,9]
 * 输出
 * 3
 * 说明
 * 一开始有3个数字，分别为9，4，9，x为7，操作这3个数字后每个数字都不小于x
 * 示例2
 * 输入
 * 2,5,[4,3]
 * 输出
 * 0
 * 说明
 * 一共2个数字，无论怎么操作都不会大于等于x
 * <p>
 * 备注:
 * 1 \leq n \leq 10^{6}，1≤n≤10
 * 6
 * ，
 * 1 \leq x \leq 10^{9}，1≤x≤10
 * 9
 * ，
 * a_{1},a_{2},a_{3}...a_{n}(1 \leq a_{i} \leq 10^{9})代表数组中元素a
 * 1
 * ​
 * ,a
 * 2
 * ​
 * ,a
 * 3
 * ​
 * ...a
 * n
 * ​
 * (1≤a
 * i
 * ​
 * ≤10
 * 9
 * )代表数组中元素
 * 对于25\%的数据,1 \leq n \leq 10^{2},1 \leq x,a_{i} \leq 10^{3}对于25%的数据,1≤n≤10
 * 2
 * ,1≤x,a
 * i
 * ​
 * ≤10
 * 3
 * <p>
 * 对于75\%的数据,1 \leq n \leq 10^{4},1 \leq x,a_{i} \leq 10^{6}对于75%的数据,1≤n≤10
 * 4
 * ,1≤x,a
 * i
 * ​
 * ≤10
 * 6
 * <p>
 * 对于100\%的数据,1 \leq n \leq 10^{6},1 \leq x,a_{i} \leq 10^{9}对于100%的数据,1≤n≤10
 * 6
 * ,1≤x,a
 * i
 * ​
 * ≤10
 * 9
 */
public class MouMou {

    // 思路：先排序，从最大那头开始一直往里加数，求平均值，直到平均值小于x时停止，返回加入数的个数。
    public int arrange(int n, int x, int[] a) {

        if (a.length == 0) {
            return 0;
        }

        Arrays.sort(a);

        int lastLessThanX = 0; // 找出第一个大于x的下标；

        long sum = 0; // 计算总和

        int count = 0; //总和中元素个数

        boolean all = true; // 判断是否所有符合的标志

        for (int i = a.length - 1; i >= 0; i--) {
            sum += a[i];
            count++;
            if (sum / count < x) {
                all = false;
                break;
            }
        }

        if (!all) {
            count--;
        }

        return count;
    }

}
